package top.humbleyuan.dichotomy;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:50
 * @Des 搜索二维数组
 */
public class LeetCode_Interview_10_09 {
    public static void main(String[] args) {
        // 类似二分法
        int[][] nums = {
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };

        int target = 100;

        /**
         * 根据结构确定思路：
         * 每次和一个数比较时
         * 所以可以从右上角或者左下角开始逐步剔除行或列
         */
        // 从右上角开始
        int curI = 0;
        int curJ = nums[0].length - 1;

        while(curI < nums.length && curJ >= 0) {
            if(nums[curI][curJ] == target) {
                System.out.println(true);
                return;
            }

            if(nums[curI][curJ] > target) {
                curJ--;
                continue;
            }

            if(nums[curI][curJ] < target) {
                curI++;
            }
        }

        System.out.println(false);
    }
}
